package com.salim.leetcode.$81;

public class SearchInRotatedSortedArrayII {
    public boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            //去重
            while(left+1<nums.length&&nums[left+1]==nums[left]){
                left++;
            }
            //去重
            while(right-1>=0&&nums[right-1]==nums[right]){
                right--;
            }

            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) {
                    //去重
                    while(mid+1<nums.length&&nums[mid+1]==nums[mid]){
                        mid++;
                    }
                    left = mid + 1;
                } else {
                    //去重
                    while(mid-1>=0&&nums[mid-1]==nums[mid]){
                        mid--;
                    }
                    right = mid - 1;
                }
            } else {
                if (nums[left] <= target && target < nums[mid]) {
                    //去重
                    while(mid-1>=0&&nums[mid-1]==nums[mid]){
                        mid--;
                    }
                    right = mid - 1;
                } else {
                    //去重
                    while(mid+1<nums.length&&nums[mid+1]==nums[mid]){
                        mid++;
                    }
                    left = mid + 1;
                }
            }
        }
        return false;
    }
}
